package com.cuz.daileetcode.暴力递归记忆化搜索动态规划;

/**
 * @author cuzz
 * @version 1.0
 * @description: 见 【暴力递归-记忆化搜索-动态规划3】
 * @date 14:26 2022/1/9
 **/
public class HorseJumpToTargetPosition {
    public static void main(String[] args) {
        int x = 6;
        int y = 6;
        int step = 10;
        System.out.println(Recursion.horseJumpToTargetPosition(x, y, step));
        System.out.println(DynamicProgramming.horseJumpToTargetPosition(x, y, step));
    }

    static class Recursion {

        static int horseJumpToTargetPosition(int x, int y, int step) {
            return recursion(x, y, step);
        }

        /***
         * 起始位于0 0 去往目标位置 x y 必须走step步
         *
         * 但是代码的写法是从 x，y 跳向 0 ，0用step步
         * 二者等价
         * @param x 目标位置的横坐标
         * @param y 目标位置的纵坐标
         * @param step 需要走多少步
         * @return 一共多少中走法
         */
        static int recursion(int x, int y, int step) {
            //如果越界那么说明当前递归树的分支不得行
            if (!checkPosition(x, y)) {
                return 0;
            }
            //如果步数用完了
            if (step == 0) {
                //是在 0 0 位置 那么是一种跳法
                if (x == 0 && y == 0) {
                    return 1;
                } else {
                    //反之此跳法不得行
                    return 0;
                }
            }
            return  //假如当前位置（6，6）依赖于（5，8）(7,8),(8,7),(8,5)(5,4),(4,5),(4,7)
                    recursion(x - 1, y + 2, step - 1)
                            + recursion(x + 1, y + 2, step - 1)
                            + recursion(x + 2, y + 1, step - 1)
                            + recursion(x + 2, y - 1, step - 1)
                            + recursion(x + 1, y - 2, step - 1)
                            + recursion(x - 1, y - 2, step - 1)
                            + recursion(x - 2, y - 1, step - 1)
                            + recursion(x - 2, y + 1, step - 1)
                    ;

        }


    }


    /**
     * 检查马儿当前位置是否越界 跳出棋盘外
     *
     * @param x 横坐标
     * @param y 纵坐标
     * @return 是否越界 越界返回false
     */
    private static boolean checkPosition(int x, int y) {
        return x >= 0 && x <= 8 && y >= 0 && y <= 9;
    }

    static class DynamicProgramming {

        static int getValueOfDpArrayOutBoundReturn0(int[][][] dp, int x, int y, int step) {
            try {
                return dp[x][y][step];
            } catch (Exception e) {
                return 0;
            }
        }

        static int horseJumpToTargetPosition(int x, int y, int step) {
            //目标位置太离谱。需要花完的步数不符合实际 返回0
            if (!checkPosition(x, y) || step < 0) {
                return 0;
            }
            int[][][] dp = new int[8 + 1][9 + 1][step + 1];
            dp[0][0][0] = 1;
            for (int curLayer = 1; curLayer <= step; curLayer++) {
                for (int curX = 0; curX <= 8; curX++) {
                    for (int curY = 0; curY <= 9; curY++) {
                        ///假如当前位置（6，6）依赖于（5，8）(7,8),(8,7),(8,5)(5,4),(4,5),(4,7)
                        //curLayer=6 表示6步到（6，6） 右多少种方法，
                        //方法总数等于 用五步到5，8）(7,8),(8,7),(8,5)(5,4),(4,5),(4,7)存在多少种方法
                        dp[curX][curY][curLayer] =
                                getValueOfDpArrayOutBoundReturn0(dp, curX - 1, curY + 2, curLayer - 1)
                                        + getValueOfDpArrayOutBoundReturn0(dp, curX + 1, curY + 2, curLayer - 1)
                                        + getValueOfDpArrayOutBoundReturn0(dp, curX + 2, curY + 1, curLayer - 1)
                                        + getValueOfDpArrayOutBoundReturn0(dp, curX + 2, curY - 1, curLayer - 1)
                                        + getValueOfDpArrayOutBoundReturn0(dp, curX + 1, curY - 2, curLayer - 1)
                                        + getValueOfDpArrayOutBoundReturn0(dp, curX - 1, curY - 2, curLayer - 1)
                                        + getValueOfDpArrayOutBoundReturn0(dp, curX - 2, curY - 1, curLayer - 1)
                                        + getValueOfDpArrayOutBoundReturn0(dp, curX - 2, curY + 1, curLayer - 1);
                    }
                }
            }
            return dp[x][y][step];
        }

    }
}
